perm filename GEM[0,BGB]8 blob
sn#092011 filedate 1974-03-15 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00013 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 3.0 Geometric Modeling Theory.
C00008 00003 3.1 Kinds of Geometric Models.
C00013 00004
C00015 00005
C00018 00006 3.X Polyhedron Modeling.
C00037 00007 3.X The Vertex.
C00041 00008 3.X The Edge.
C00044 00009 3.X The Face.
C00047 00010 3.X Three kinds of perimeters.
C00053 00011 3.X Accessing.
C00056 00012 3.X Camera Model.
C00060 00013 3.X Light Scattering Model
C00062 ENDMK
C⊗;
3.0 Geometric Modeling Theory.
3.0 Introduction.
Geometric modeling literally means representing the
measurement of the earth. In the specific context of computer vision
and graphics, geometric modeling refers to constructing computer
representations of physical objects, cameras, images and light for
the sake of numerically simulating their behavior in space and time.
Ignoring subtleties, geometric world modeling is distinguished from
semantic and logical modeling in that it is quantitative and
numerical rather than qualitative and symbolic. Practical modeling
issues involve which aspects of the world are significant; which
programming technologies should be used; and what are the trade offs
between storing the model and recomputing the model. In this chapter,
the theory of geometric modeling begins in the abstract deep of space
and time and ends in the experimental shallow of the basics
concerning cameras, light, polyhedra, faces, edges and vertices.
3.1 Kinds of Geometric Models.
In mechnical engineering, objects are represented by drawings
and pictures, which begs the question. In mathematics and physics,
particular complicated shapes do not occur per se. Thus although we
are now late into the twentieth century, there is still no accepted
good method for expressing the geometry of an arbitrary physical
object in a computer. The scope of the problem can be appreciated by
examining the virtues and drawbacks of the methods listed in the box.
---------------------------------------------------------
| Some kinds of geometric models: |
| |
| Space Oriented: |
| |
| 1. 3-D Space Array. |
| 2. Recursive Cells. |
| 3. 3-D Density Function. |
| 4. 2-D Surface Functions. |
| 5. Parametric Surface Functions. |
| |
| Object Oriented: |
| |
| 6. Manifolds. |
| 7. Polyhedra. |
| 8. Volume Elements. |
| 9. Cross Sections. |
| 10. Skeletons. |
---------------------------------------------------------
For a naive start, first consider a 3-D array in which each
element indicates the presence or absence of solid matter in a cube
of space. Such a 3-D space array has the very desirible properties
of "spatial addressing" and "spatial uniqueness" in their most direct
and natural form. Spatial addressing refers to finding out what the
model contains within a distance R of a locus X,Y,Z; spatial
uniqueness refers to modeling the property that physical solids can
not occupy the same space. The main drawback of the 3-D space array
model is illustrated by the apparently legal FORTRAN statement:
DIMENSION SPACE(10000,10000,10000)
Although, no present day computer memory is large enough to contain a
10↑15 element array; smaller space arrays are used for weather, wind
tunnels, and stress analysis. A further drawback of space arrays is
that objects and surfaces are not readily available.
The space array idea can be salvaged (and must be salvaged)
by noticing that large portions of the array contain similair values.
By grouping blocks of elements with the same values together, the
addressing process becomes more complicated but the overall memory
required is greatly reduced and the two desired peoperties are not
lost. The one true way of doing this (which has been discovered in
several applications and claimed as an original contribution by
numerous authors) is "recursive cells"; the whole space is considered
to be a cell (if the space is not homogeneous than the cell is
divided into two (or four or eight) sub cells and the criterion is
applied again. This technique of recursive celling is of fundamental
importance because it allows for the spatial sorting of objects, if
and only if the object models can be conveniently subdivided by
cutting planes.
Analytically, an arbitrary object can be represented as a
three dimensional density function W = RHO(X,Y,Z) or as a two
dimensional surface funtion Z = F(X,Y). The usual form of function
notation (short of a programming language or an extensive table) is
inadequate for describing complicated physical objects. Since the
definition of a function is that it is single valued; the discription
of an object requires a set functions each with specific domain,
which brings us to the celebrated mathematical topic: the algebraic
topology of locally Euclidean transitions of infinitely
differentiable oriented Riemann manifolds.
A manifold is the mathematical abstraction of a surface; a
Riemann manifold has a metric function; an oriented manifold has a
unambiguous inside and an outside; and the phrase "infinitely
differentiable" can be taken to mean that the surface is smooth and
continuous.
Geometrically, a solid rigid opaque object can be enclosed by
an unbroken two dimensional surface with an unabiguous inside and
outside. Objects can be moved about in space, but two objects can not
simultaneously occupy the same space.
Arbitrary objects can also be described by listing a set of
cross sectional polygons taken at a sufficient number of cutting planes;
this is how the shape of a ship's hull or an airplane's wing is specified.
Forsaking arbitrary shaped objects, large classes of
things can be described in terms of a small set of basic volume elements.
For example, Roberts and others have built models of familair objects
using only rectangular and triangular right prisms. (Although, arbitrary
solid polyhedra can be constructed out of tetrahedrons, the 3-simplex;
no large modeling system exists using this approach).
Skeletal models are based on abstracting an object into a stick figures
and by associating a diameter or set of cross sections with the sticks.
In particular, spine cross section models have been pursued at
Stanford by (Agin, Binford and Nervatia; Blum) for the sake of
object recognition.
Finally, it is often useful to represent objects by a very
weak model such as by using sets of spheres or sets of surface
points. It is interesting to note that the "ultimate reality" that
Winograd's thesis robot SRDL could talk about, was a blocks world based
on a geometric model consisting of points, size of block, and a
two paged LISP routine name FINDSPACE.
To the best of my knowledge, this survey is complete;
there are no other significantly different kinds of geometric models.
3.X Polyhedron Modeling.
In elementary geometry, a polyhedron is said to be a solid
formed (or bounded) by plane faces.
Topologically, simple polyhedra satisfy
Euler's F-E+V=2 equation; where F, E and V are the number of faces,
edges and vertices of the polyhedron respectively. This equation was
known to Descartes in 1640, but the first proof wasn't given until
1752, when Euler proved the relation by considering the graph
corresponding to the edges of polyhedra. A simple polyhedron is one
homeomorphic to a sphere.
_____________________________________________________________________
PRACTICAL SOLID POLYHEDRON CONDITIONS:
1. Satisfies Eulers Equation F-E+V=2*B-2*H
2. All vertives and faces have three or more edges.
3. No edge intersects a face or vertex
to which it doesn't belong.
4. All the vertices of a face are coplanar.
_____________________________________________________________________
3.X The Vertex.
A vertex is a labeled point in a Euclidean three
space. The important thing about a vertex is its world locus (with
component names XWC,YWC,ZWC standing for world-coordinates). Vertex
locii are the basic geometric data from which length, area, volume,
face vectors and image positions can be computed.
Also a Vertex may
exist simultaneously in one or more image spaces. An image space
(with component names XPP,YPP,ZPP standing for perspective-projected)
is always three dimensional and is determined with respect to a given
camera centered coordinate system (with component names XCC,YCC,ZCC
standing for camera-coordinates). The third image component, ZPP,
is taken inversely proportional to the distance of the vertex from
the camera image plane, ZCC. Using the camera of the previous
section. The transformation of a vertex world locus to a camera
centered locus is:
X ← XWC - CX;
Y ← YWC - CY;
Z ← ZWC - CZ;
XCC ← IX*X + IY*Y + IZ*Z;
YCC ← JX*X + JY*Y + JZ*Z;
ZCC ← KX*X + KY*Y + KZ*Z;
The first three assignment statements are the translation to
the camera frame's origin, the second three assignments are the
rotation to the camera frame's orientation. Next the perspective
projection transformation is computed:
XPP ← SCALEX*XCC/ZCC;
YPP ← SCALEY*YCC/ZCC;
ZPP ← SCALEZ /ZCC;
The XPP and YPP assignments are derived by means of similar
triangles, as is being done by the man in figure 1.5; the Zpp
assignment is for preserving the depth information and the
colinearity of the world in the perspective projected image space. As
given, the PP frame is right handed and vertices in front of the
camera's image plane will have negative Zpp; Zpp values near -FOCAL
are close to the camera and values approaching zero are far away.
A final matter with respect to vertices is their valence. The
valence of a vertex is the number of edges that meet at the vertex. A
vertex valence of three, for example, indicates a trihedral corner.
3.X The Edge.
For a start, the structure of an edge need be thought of as
little more than two vertices; the topological subtlety of edges will
be explained later. However, two vertices do define the important
geometric edge data called the line coefficients. Named AA, BB,
CC; these coefficients are computed from the perspective locus of the
edge's endpoints as follows:
AA ← Y1 - Y2;
BB ← X2 - X1;
CC ← X1*Y2 - X2*Y1;
These coefficients appear in the 2D equation of the line that
contains the edge:
0 = AA*X + BB*Y + CC;
When the edge coefficients are normalized:
L ← SQRT(AA↑2+BB↑2);
AA ← AA/L;
BB ← BB/L;
CC ← CC/L;
the line equation gives the distance, of a point X,Y from the line:
Q ← AA*X + BB*Y + CC;
The distance is actually ABS(Q), since Q is negative on one side side
of the line; also if one were standing on the plane at point X1,Y1
facing X2,Y2 the Q positive half-plane would be on your left and the
Q negative half plane would be on your right.
An important operation on two edges is to detect whether or
not they intersect; this can be decided by checking first whether the
endpoints of one edge are in the opposite half planes of the other
edge, and second whether the endpoints of the latter edge are in the
opposite half planes of the first. When both conditions obtain, then
the intersection point can be found:
T ← (A1*B2 - A2*B1);
X ← (B1*C2 - B2*C1)/T;
Y ← (A2*C1 - A1*C2)/T;
An actual compare for intersection should initially check for the
identity case, and for edges with a vertex in common.
3.X The Face.
A face is a finite region of plane enclosed by straight
lines. A safe formal face structure could be built by defining a
triangle as three non-colinear vertices and then insisting that all
faces be triangle interiors. Unhappily, BFEV faces are usually
represented as a list of vertices and edges (or by something nearly
equivalent) for the sake of saving memory space. Such `list' faces
are not monolithic but tend to suffer special cases and pathologies
such as:
Coincident or crossing edges,
Holes and Disjointness,
Concavity (& Convexity),
Non-coplanarity.
Like edges, faces have characteristic coefficients. Face coefficients
satisfy the equation of a plane in which the face is embedded:
AA*X + BB*Y + CC*ZZ = KK.
The equation could be divided by KK, but that is undesirable because
the AA, BB, CC are more useful as a unit normal vector, in which case
KK is the distance of the origin from the plane. Given the locii of
three non-colinear vertices, the coefficients of a plane can be
computed by Kramer's rule as follows:
KK ← X1*(Z2*Y3-Y2*Z3)
+ Y1*(X2*Z3-Z2*X3)
+ Z1*(Y2*X3-X2*Y3);
AA ← (Z1*(Y2-Y3) + Z2*(Y3-Y1) + Z3*(Y1-Y2));
BB ← (X1*(Z2-Z3) + X2*(Z3-Z1) + X3*(Z1-Z2));
CC ← (X1*(Y3-Y2) + X2*(Y1-Y3) + X3*(Y2-Y1));
and normalized:
ABC ← SQRT(AA↑2 + BB↑2 + CC↑2);
AA ← AA/ABC;
BB ← BB/ABC;
CC ← CC/ABC;
KK ← KK/ABC;
If the given vertices V1, V2, V3 had been taken going counter
clockwise about the face as viewed from the exterior of the solid,
then the following relations obtain:
AA*X + BB*Y + CC*Z > KK implies X,Y,Z above the plane.
AA*X + BB*Y + CC*Z = KK implies X,Y,Z in the plane.
AA*X + BB*Y + CC*Z < KK implies X,Y,Z below the plane.
Face coefficients prove useful in both world and image coordinates.
3.X Three kinds of perimeters.
FACE PERIMETER - a face is surrounded by edges and vertices.
VERTEX
⊗
/ \
/ \
/ \
/ \
EDGE / \ EDGE
/ \
/ FACE \
/ \
/ \
/ \
VERTEX ⊗---------------------⊗ VERTEX
EDGE
VERTEX PERIMETER - a vertex is surrounded by edges and faces.
EDGE
|
|
FACE | FACE
|
⊗ VERTEX
/ \
/ \
/ \
/ \
/ FACE \
EDGE EDGE
EDGE PERIMETER - an edge is surrounded by 2 faces & 2 vertices.
VERTEX
⊗
|
|
FACE E FACE
|
|
⊗
VERTEX
3.X Accessing.
A BFEV model has four kinds of accessing. The most
conventional BFEV access is retrieval by symbolic name which requires
a symbol table. Next, between bodies there is Parts-Tree accessing.
At the top of the Parts-Tree is a special body named the world to
which all the other bodies are attached; thus the world body serves
as an OBLIST node. Given a particular body, a list of its sub-parts
can be retrieved as well as its supra-part or "supart". A supart is
the whole entity to which a part belongs, the world being its own
supart.
Within each body there is face, edge and vertex sequential
accessing. Given a body, all its faces, or edges, or vertices need to
be readily available since perspective projection loops thru all the
vertices, and the process of display clipping loops thru all the
edges, and the act of checking for body intersection loops thru all
the faces.
Finally, among the faces, edges and vertices of a body there
is perimeter accessing. Faces have a perimeter of edges and vertices
[figure 1.6]; less commonly used, vertices have a perimeter of edges
and faces [figure 1.7]; and of particular note, edges have a
perimeter always formed by two faces and two vertices, [figure 1.8].
Perimeter accessing requires that given a face, edge or vertex, that
the perimeter of that entity be readily accessible. Since the surface
of a polyhedron is orientable, that is has a well defined inside and
outside, (Klein bottles with their crosscaps will not be modeled),
such perimeter lists can be ordered (say clockwise) with respect to
the exterior of the polyhedron. Perimeter accessing is mentioned in
Guzman and Falk and is the underlying
basis of part-II of this paper which presents a polyhedron model
built for accessing and altering face, edge and vertex perimeters.
3.X Camera Model.
The particular camera model I have been using, is
expressed by eighteen real numbers involving nine degrees of freedom.
First there is the camera lens center locus:
CX, CY, CZ, in world coordinates.
Afixed to the lens center is the camera frame of reference with unit
vectors i, j and k. When the image formed by the camera is placed in
correspondence to a display screen, as illustrated in figure 1.3, the
unit vector i maps into the rightward positive x of the display
screen, and the unit vector j maps into the upward positive y of the
display screen, and the unit vector k comes out of the display screen
to form a right handed coordinate system. Together the three unit
vectors of the camera are the three by three rotation matrix:
IX, IY, IZ
JX, JY, JZ in world coordinates.
KX, KY, KZ
Next, there are three scales which determine the correspondence
between world size and image size. Observe that the world is measured
in physical units of length like meters or feet while computer images
come in integral sizes like 1024 by 1024 or 480 rows by 512 columns,
thus the conversion scales must be in terms of logical image units
per physical world units. In an actual television camera a minute
image (say 9mm by 12mm) is formed on a vidicon tube and that image
has a particular number of rows and columns. It is the little image
on the vidicon that we pretend to model by the six parameters:
LDX, LDY, LDZ Logical raster size.
PDX, PDY, FOCAL Physical raster size.
Where the number named FOCAL, is the focal plane distance which in
this model (with distant objects) can safely be equated with the lens
focal length and can be given in millimeters (conventional lens run
12.5mm to 75mm for 1" TV). The integer LDZ is an artifact so that
the units come out correctly in the Z dimension. Thus the scales
factors are defined:
SCALEX ← -FOCAL*LDX/PDX;
SCALEY ← -FOCAL*LDY/PDY;
SCALEZ ← FOCAL*LDZ;
This simple camera model is used to compute vertex image
coordinates.
3.X Light Scattering Model
The light scattering properties of ordinary surfaces can be
modeled by thinking of the surface as composed of zillions of little
differential mirrors. The orientation of each mirror is described by
two angles, its tilt from the normal vector of the surface and its
pan about the normal vector with respect to a specified reference
vector in the tangent plane of the surface. For a perfect reflecting
surface all the differential mirrors have a zero pan and tilt; for
isotropic conventional surfaces the statistical distribution of pan
orientations is flat and the distribution of tilt orientations is a
blip function; and for a perfect isotropic Lambert surfaces both the
pan and tilt distributions are flat.